package com.leetcode.alibaba;

import java.util.ArrayList;
import java.util.List;

/**
 * 重复计算次数太多，比如n=8，程序会去计算F(7)和F(6)
 * 为了计算F(7),程序又会再去计算F(6)和F(5),这样就重复计算了已知值
 * 时间开销大，并且容易栈溢出。
 */
public class 斐波那契数列 {
	public int Fibonacci(int n) {
		if (n == 0) {
			return 0;
		}
		if (n == 1) {
			return 1;
		}
		return Fibonacci(n - 1) + Fibonacci(n - 2);
	}

	/**
	 * 优化：用一个数组将每个值存起来，需要的时候直接取，不用重复计算
	 */
	public int Fibonacci1(int n) {
		List<Integer> list = new ArrayList();
		if (n <= 1) {
			return list.get(n);
		} else {
			for (int i = 2; i <= n; i++) {
				list.add(list.get(i - 1) + list.get(i - 2));
			}
			return list.get(n);
		}
	}
}
